#include <bits/stdc++.h>
using namespace std;

/*
1922. 统计好数字的数目
已解答
中等
相关标签
相关企业
提示
我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。

比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。
给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。

一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。

 

示例 1：

输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
示例 2：

输入：n = 4
输出：400
示例 3：

输入：n = 50
输出：564908303
 

提示：

1 <= n <= 1015
*/

//
class Solution {
	public:
	using ll = long long;
	int countGoodNumbers(long long n) {
		const int MOD = 1e9 + 7;
		ll event_count = (n + 1) / 2;   // 偶数
		ll odd_count = n / 2;

		// 计算数量 % 
		ll part1 = fastPow(5, event_count, MOD);
		ll part2 = fastPow(4, odd_count, MOD);

		return (part1 * part2) % MOD;
	}
	ll fastPow(ll num, ll event_count, ll MOD) {
		ll ans = 1;
		num %= MOD; // 防止溢出
		while (event_count > 0) {
			if (event_count % 2 == 1) {
				// 二进制位数为1就累乘
				ans = (ans * num) % MOD;
			}
			num = (num * num) % MOD;// 平方并取模
			event_count /= 2;// 右移处理下一位
		}
		return ans;
	}
};

// 优化
class Solution {
	private:
	static constexpr int mod = 1000000007;
	// 定义模数常量，防止计算结果溢出（使用小写符合当前代码风格）
	// 10^9 + 7
	
public:
	/**
	 * 计算满足条件的"好数字"字符串数量
	 * @param n 数字字符串的长度
	 * @return 符合条件的好数字数量，结果对mod取模
	 * 
	 * 算法思路：
	 * 1. 偶数下标位置（0-based）只能填5种偶数数字（0,2,4,6,8）
	 * 2. 奇数下标位置只能填4种质数数字（2,3,5,7）
	 * 3. 总数 = (5^偶数位数量) * (4^奇数位数量)
	 */
	int count(long long n) {
		// 快速幂模板函数（lambda实现）
		auto quickmul = [](int x, long long y) -> int {
			int ret = 1;        // 初始化结果为乘法单位元1
			int mul = x;        // 当前基数
			while (y > 0) {
				// 当二进制位为1时，累乘当前基数
				if (y % 2 == 1) {  // 等价于 (y & 1)
					ret = (long long)ret * mul % mod;
				}
				// 基数平方并取模（防止溢出）
				mul = (long long)mul * mul % mod;
				// 处理下一位二进制（右移等价于除以2）
				y /= 2;          // 等价于 y >>= 1
			}
			return ret;
		};
		
		// 计算偶数位数量（ceil(n/2)）
		long long even_positions = (n + 1) / 2;
		// 计算奇数位数量（floor(n/2)）
		long long odd_positions = n / 2;
		
		// 合并计算结果：(5^even * 4^odd) % mod
		return (long long)quickmul(5, even_positions) * quickmul(4, odd_positions) % mod;
	}
};